<h2>题目编号 : 149</h2>
<div style="color:#666;font-size:80%;">13 April 2007</div><br />
<div class="problem_content">
<p>Looking at the table below, it is easy to verify that the maximum possible sum of adjacent numbers in any direction (horizontal, vertical, diagonal or anti-diagonal) <span style="white-space:nowrap">is 16 (= 8 + 7 + 1).</span></p>

<div style="text-align:center">
<table border="1" cellpadding="6" cellspacing="0" style="margin:auto"><tbody align="right"><tr><td><img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />2</td ><td >5</td><td>3</td><td>2</td></tr>
<tr><td>9</td><td><img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />6</td><td>5</td><td>1</td></tr>
<tr><td>3</td><td>2</td><td>7</td><td>3</td></tr>
<tr><td><img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />1</td><td>8</td><td><img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />4</td><td>&nbsp; 8</td></tr></tbody></table>
</div>

<p>Now, let us repeat the search, but on a much larger scale:</p>

<p>First, generate four million pseudo-random numbers using a specific form of what is known as a "Lagged Fibonacci Generator":</p>

<p>For 1 <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> <i>k</i> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> 55, <i>s</i><img src="" style="display:none;" alt="_(" /><sub><i>k</i></sub><img src="" style="display:none;" alt=")" /> = [100003 <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' /> 200003<i>k</i> + 300007<i>k</i><img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" />] (modulo 1000000) <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' /> 500000.<br />
For 56 <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> <i>k</i> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> 4000000, <i>s</i><img src="" style="display:none;" alt="_(" /><sub><i>k</i></sub><img src="" style="display:none;" alt=")" /> = [<i>s</i><img src="" style="display:none;" alt="_(" /><sub><i>k<img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />24</i></sub><img src="" style="display:none;" alt=")" /> + <i>s</i><img src="" style="display:none;" alt="_(" /><sub><i>k<img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />55</i></sub><img src="" style="display:none;" alt=")" /> + 1000000] (modulo 1000000) <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' /> 500000.</p>

<p>Thus, <i>s</i><img src="" style="display:none;" alt="_(" /><sub>10</sub><img src="" style="display:none;" alt=")" /> = <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />393027 and <i>s</i><img src="" style="display:none;" alt="_(" /><sub>100</sub><img src="" style="display:none;" alt=")" /> = 86613.</p>

<p>The terms of <i>s</i> are then arranged in a 2000<img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' />2000 table, using the first 2000 numbers to fill the first row (sequentially), the next 2000 numbers to fill the second row, and so on.</p>

<p>Finally, find the greatest sum of (any number of) adjacent entries in any direction (horizontal, vertical, diagonal or anti-diagonal).</p>
</div><br />
